//
// Created by PC on 2024/4/26.
//


#include <iostream>
#include "arrUtil.h"
using namespace std;

// 分成小于等于区和大于区 以第一个数为基准
int part(int * a,int l, int r)
{
    int le=l;
    int cur = a[l];
    for (int i = l+1; i <=r ; ++i)
    {
        if(a[i]<=cur)
        {
            ++le;
            swap(a[i],a[le]);
        }
    }
    swap(a[le],a[l]);
    return le;
}

void quickSort(int * a, int l, int r)
{
    if(l<r)
    {
        int m = part(a,l,r);
        quickSort(a,l,m-1);
        quickSort(a,m+1,r);
    }
}
int main()
{
//    int arr[]{7,9,8,7,4,3,3,6};
//    cout<<part(arr,0,7)<<endl;
    int n = 1000;
    int arr[1000];
    randomArr(arr,n);
    quickSort(arr,0,n-1);
//    printArr(arr,n);
    cout<<checkSort(arr,n);
    return 0;
}